package com.maduar.demo.algo.interview.dp;

/**
 * Description:   铜条切割 Iron rod
 *
 * @author maduar maduar@163.com
 * @date 2021-04-05 13:10
 */
public class IronRod {

    private IronRod() {
    }

    /**
     * 1. 接口名称: 动态规划-钢条切割
     * 2. 接口文档编号: 算法导论第四版15.1
     * 3. 接口详细说明: 递归
     *
     * @param lArr 铜条长度
     * @param n 铜条个数
     * @return int 最大价值
     * @Author: danny.pang
     * @Date: 2021-04-05 13:16:18
     */
    public static int cutRod(int[] lArr, int n) {
        if (n == 0) {
            return 0;
        }

        int q = -1;

        for (int i = 1; i <= n; i++) {
            q = Math.max(q, lArr[i] + cutRod(lArr, n - i));
        }

        return q;
    }

    /**
     * 1. 接口名称: 动态规划-钢条切割
     * 2. 接口文档编号: 算法导论第四版15.1
     * 3. 接口详细说明: 递归 - 带备忘录的自上向下
     *
     * @param lArr 铜条长度
     * @param n 铜条个数
     * @return int 最大价值
     * @Author: danny.pang
     * @Date: 2021-04-05 13:16:18
     */
    public static int cutRodWithMemoryTopToDown(int[] lArr, int n) {
        int[] r = new int[n + 1];
        for (int i = 0; i <= n ; i++) {
            r[i] = -1;
        }
        return cutRodWithMemoryTopToDown(lArr, n, r);
    }

    private static int cutRodWithMemoryTopToDown(int[] lArr, int n, int[] r) {
        if (r[n] >= 0) {
            return r[n];
        }

        int q = 0;
        if (n > 0){
            for (int i = 1; i <= n; i++) {
                q = Math.max(q, lArr[i] + cutRodWithMemoryTopToDown(lArr, n - i, r));
            }
        }

        r[n] = q;
        return q;
    }

    /**
     * 1. 接口名称: 动态规划-钢条切割
     * 2. 接口文档编号: 算法导论第四版15.1
     * 3. 接口详细说明: 递归 - 带备忘录的自底向下
     *
     * @param lArr 铜条长度
     * @param n 铜条个数
     * @return int 最大价值
     * @Author: danny.pang
     * @Date: 2021-04-05 13:16:18
     */
    public static int cutRodDownToTop(int[] lArr, int n) {

        int[] dp = new int[n + 1];
        int q = 0;

        for (int j = 1; j <= n; j++) {
            q = -1;
            for (int i = 1; i <= j; i++) {
                q = Math.max(q, lArr[i] + dp[j - i]);
            }
            dp[j] = q;
        }

        return dp[n];
    }

}
